package me.helllp.book.concurrent.ch05;

import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 希尔排序并行算法演示
 * 
 * @author Administrator
 *
 */
public class ShellOrderDemo {
	static int arr[];
	
	static {
		arr = new int[1000000];
		
		Random rand = new Random();
		
		for(int i=0; i<arr.length; i++){
			arr[i] = Math.abs(rand.nextInt());
		}
	}
	
	public static void shellSort(){
		int h = 1;
		while(h <= arr.length / 3){
			h = h * 3 + 1;
		}
		
		while(h > 0){
			for(int i=h; i<arr.length; i++){
				if(arr[i] < arr[i-h]){
					int temp = arr[i];
					int j = i -h;
					while(j >= 0 && arr[j] > temp){
						arr[j + h] = arr[j];
						j -= h;
					}
					arr[j+h] = temp;
				}
			}
			h = (h-1) / 3;
		}
	}
	
	public static class ShellOrderTask implements Runnable{
		int start = 0; 
		int k = 0;
		CountDownLatch l;
		
		public ShellOrderTask(int start, int k, CountDownLatch l) {
			this.start = start;
			this.k = k;
			this.l = l;
		}
		
		@Override
		public void run() {
			int length = arr.length;
			
	        for(int j = start; j<length ;j=j + k){  
	            for(int m = j; m>=0 && m- k >= 0 && (arr[m] < arr[m- k]); m= m- k){
	            	int iTemp = arr[m];
	            	arr[m] = arr[m-k];
	            	arr[m-k] = iTemp;
	            }
	        }  
	        l.countDown(); 
		}
	}
	
	static ExecutorService pool = Executors.newWorkStealingPool();
	
	public static void pShellSort() throws InterruptedException{
		int h = 1;
		
		while(h <= arr.length / 3){
			h = h * 3 + 1;
		}
		
		while(h != 1){
//			System.out.println("h = " + h);
			h = h / 3;

            CountDownLatch latch = new CountDownLatch(h);  
			
            for (int i = 1; i <= h; i++) {  
            	pool.submit(new ShellOrderTask(i, h, latch));  
            }  
            
			//	等待线程排序，进入下一次排序
			latch.await();
		}
	}
	
	public static void main(String[] args) throws InterruptedException {
		long s = System.currentTimeMillis();
		shellSort();
		long e = System.currentTimeMillis();
		
		System.out.println("传统方法耗时：" + (e-s));
		
		s = System.currentTimeMillis();
		pShellSort();
		e = System.currentTimeMillis();

		System.out.println("并行算法耗时：" + (e-s));
		
		for(int i=0; i<100; i++){
			System.out.println(arr[i]);	
		}		
	}
}
